import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/9 10:01
 * @description 动态规划
 */
public class Solution2 {
    public static void main(String[] args) {

    }
    int MAX = Integer.MAX_VALUE;
    public int minFallingPathSum(int[][] mat) {
        int n = mat.length;
        // f[i][j] 到达位置i,j的最短路径和
        int[][] f = new int[n][n];
        // 初始化，对于首行而言，每个位置的最小成本为其矩阵值
        for (int i = 0; i < n; i++) {
            f[0][i] = mat[0][i];
        }
        // 从第二行开始，根据题目给定的条件进行转移
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int val = mat[i][j];
                f[i][j] = f[i - 1][j] + val;
                if (j - 1 >= 0) {
                    f[i][j] = Math.min(f[i][j], f[i-1][j-1] + val);
                }
                if (j + 1 <  n) {
                    f[i][j] = Math.min(f[i][j], f[i-1][j+1] + val);
                }
            }
        }
        int ans = MAX;
        for (int i = 0; i < n; i++) {
            ans = Math.min(ans, f[n-1][i]);
        }
        return ans;
    }
}
